<!--
 * @Author: zengwj
 * @Date: 2021-09-23 14:02:22
 * @LastEditors: zengwj
 * @LastEditTime: 2021-09-23 14:24:45
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      //       输入: k = 3, n = 9
      // 输出: [[1,2,6], [1,3,5], [2,3,4]]
      const result = [];
      const path = [];
      var combinationSum3 = function (k, n) {
        backtracking(k, n, 1, limit);
        return result;
      };
      const backtracking = function (k, n, start) {
        const limit = n - path.length < 9 ? n - path.length : 9;
        if (path.length === k) {
          const res = path.reduce((cur, pre) => cur + pre, 0);
          if (res === n) {
            result.push([...path]);
          }
          return;
        }
        for (let i = start; i <= limit; i++) {
          path.push(i);
          backtracking(k, n, i + 1);
          path.pop();
        }
      };
      console.log(combinationSum3(2, 18));
    </script>
  </body>
</html>
